using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using graph;

namespace Lab1
{
    enum DIR { UP, DOWN };

    // This is the pair tuple
    class NodeDir
    {
        public Node node;
        public DIR direction; // UP = 0 DOwn 1
        public NodeDir(Node node, DIR direction)
        {
            this.node = node;
            this.direction = direction;
        }
    }

    // This is the actual worker class
    class prune
    {
        // This will union two dictionaries together
        public static Dictionary<String, Node> DictionaryUnion(Dictionary<String, Node> a, Dictionary<String, Node> b)
        {
            Dictionary<String, Node> result = a;

            foreach (Node item in b.Values)
            {
                if (!result.ContainsKey(item.Name))
                {
                    result.Add(item.Name, item);
                }
            }
            return result;
        }

        // This will union a dictionary and a list together into a dictionary
        public static Dictionary<String, Node> DictionaryUnion(Dictionary<String, Node> a, List<Node> b)
        {
            Dictionary<String, Node> result;
            result = a;

            for (int i = b.Count - 1; i >= 0; i--)
            {
                if (!result.ContainsKey(b[i].Name))
                {
                    result.Add(b[i].Name, b[i]);
                }
            }
            return result;
        }

        // This will return all nodes reachable from the query nodes given graph and evidence nodes
        public static Dictionary<String, Node> Reachable(Graph G, Node X, Dictionary<String, Node> Observed)
        {
            // First manually clone Observed so we don't mess up with multiple calls to this function
            Dictionary<String, Node> Nodes2Visit /* L */ = new Dictionary<string, Node>();
            foreach (String k in Observed.Keys)
            {
                Nodes2Visit.Add(Observed[k].Name, Observed[k]);
            }

            // Initialize Ancestors
            Dictionary<String, Node> Ancestors = new Dictionary<string, Node>();

            while (Nodes2Visit.Count > 0) // PHASE I mark as visited all the nodes on E
            {
                IDictionaryEnumerator e = Nodes2Visit.GetEnumerator();
                e.MoveNext();
                Node Y = (Node)e.Entry.Value;
                Nodes2Visit.Remove(Y.Name);

                if (!Ancestors.ContainsKey(Y.Name))
                {
                    Nodes2Visit = DictionaryUnion(Nodes2Visit, Y.Parents);
                    Ancestors[Y.Name] = Y;
                }
            }

            //PHASE II
            Dictionary<String, NodeDir> Nodes2VisitDir = new Dictionary<string, NodeDir>();/* L */
            Dictionary<String, NodeDir> Visited = new Dictionary<string, NodeDir>();
            Dictionary<String, Node> Reachable = new Dictionary<string, Node>();

            Nodes2VisitDir.Add(X.Name, new NodeDir(X, DIR.UP));

            while (Nodes2VisitDir.Count > 0)
            {
                IDictionaryEnumerator e = Nodes2VisitDir.GetEnumerator();
                e.MoveNext();
                NodeDir Y = (NodeDir)e.Entry.Value;

                Nodes2VisitDir.Remove(Y.node.Name);
                if (!Visited.ContainsKey(Y.node.Name))
                {
                    Reachable[Y.node.Name] = Y.node;   //Y is reachable
                    Visited[Y.node.Name] = Y;
                    if (Y.direction == DIR.UP && !Observed.ContainsKey(Y.node.Name))
                    {
                        foreach (Node parent in Y.node.Parents)
                        {
                            Nodes2VisitDir[parent.Name] = new NodeDir(parent, DIR.UP);
                        }
                        foreach (Node child in Y.node.Children)
                        {
                            Nodes2VisitDir[child.Name] = new NodeDir(child, DIR.DOWN);
                        }
                    }
                    else if (Y.direction == DIR.DOWN)
                    {
                        if (!Observed.ContainsKey(Y.node.Name))
                        {
                            foreach (Node child in Y.node.Children)
                            {
                                Nodes2VisitDir[child.Name] = new NodeDir(child, DIR.DOWN);
                            }
                        }

                        if (Ancestors.ContainsKey(Y.node.Name))
                        {
                            foreach (Node parent in Y.node.Parents)
                            {
                                Nodes2VisitDir[parent.Name] = new NodeDir(parent, DIR.UP);
                            }
                        }
                    }
                }
            }
            return Reachable;
        }

        // This will further prune non-evidence nodes 
        public static Dictionary<String, Node> NonEvidenceNodesHandler(Graph G, Node X, Dictionary<string, Node> EvidenceNodes)
        {
            Dictionary<String, Node> result = new Dictionary<string, Node>();
            
            // Manually fill Dictionary
            foreach (Node n in G.Nodes.Values)
            {
                result.Add(n.Name, n);
            }

            Stack<Node> s = new Stack<Node>();
            s.Push(X);
            while (s.Count > 0)
            {
                Node curNode = s.Pop();
                // First question: Am I the end of the line?
                if (curNode.Children.Count == 0)
                {
                    // Second question: Am I an evidence node or query node?
                    if (curNode.Type == NodeType.NormalNode)
                    {
                        // First clean up children links from its parents
                        for(int i=curNode.Parents.Count-1; i>=0; i--)
                        {
                            s.Push(curNode.Parents[i]);
                            int index = curNode.Parents[i].Children.IndexOf(curNode);
                            curNode.Parents[i].Children.RemoveAt(index);
                            index = curNode.Parents.IndexOf(curNode.Parents[i]);
                            curNode.Parents.RemoveAt(index);
                        }

                        // Remove it from dictionary
                        result.Remove(curNode.Name);
                    }
                }
                else
                {
                    foreach (Node c in curNode.Children)
                    {
                        s.Push(c);
                    }
                }
            }

            return result;
        }
    }
}
